/*
*	哈希
*/



//两数之和
//https://leetcode.cn/problems/two-sum/submissions/
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        int n = nums.size();
        for(int i = 0;i<n;++i)
        {
            int num = target-nums[i];
            if(hash.count(num) && i != hash[num]) return {i,hash[num]};
            hash[nums[i]] = i;
        }
        return {-1,-1};
    }
};



//判断是否互为字符重排
//https://leetcode.cn/problems/check-permutation-lcci/submissions/
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        char hash[26] = {0};

        for(char& c:s1) ++hash[c-'a'];
        for(char& c:s2)
        {
            if(hash[c-'a'] > 0) --hash[c-'a'];
            else return false;
        }
        //for(char& n:hash) if(n > 0) return false;
        return true;
    }
};



//存在重复元素
//https://leetcode.cn/problems/contains-duplicate/description/
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> hash;

        for(int& n:nums)
        {
            ++hash[n];
            if(hash[n] == 2) return true;
        }
        return false;
    }
};



//存在重复元素II
//https://leetcode.cn/problems/contains-duplicate-ii/description/
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        int n = nums.size();
        for(int i = 0;i<n;++i) 
        {
            if(hash.count(nums[i]) && abs(i-hash[nums[i]])<=k) return true;
            hash[nums[i]]=i;
        }
        return false;
    }
};




//字母异位词分组
//https://leetcode.cn/problems/group-anagrams/description/
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hash;

        for(auto& s:strs)
        {
            string tmp = s;
            sort(tmp.begin(),tmp.end());
            hash[tmp].push_back(s);
        }
        vector<vector<string>> ret(hash.size(),vector<string>());
        int pos = 0;
        for(auto& [k,v]:hash) ret[pos++] = v;
        return ret;
    }
};



